1. Field of the Invention
The present invention relates to the optimization of code generated by a compiler, and in particular, to functional unit switching for the allocation of registers for the code being compiled.
2. Description of Related Art
An important function of an optimizing compiler is allocating physical registers to be used when code generated by the optimizing compiler is executed. Physical registers are actual hardware registers supported by the particular platform on which the code is executed. In some situations, code can be executed in the available physical registers without requiring any additional physical registers. However, in other situations, the execution of code requires more than the number of available physical registers. For example, for a sequence of instructions that performs a series of calculations, the number of intermediate values (e.g. variables, intermediate computations) which must be maintained may exceed the number of available physical registers. In this situation, another approach for allocating physical registers must be employed.
One such approach used by contemporary optimizing compilers is a multi-pass approach. In one pass, a set of virtual or "symbolic" registers is assigned to code. Virtual registers are sometimes considered to be infinite in number, but for practical reasons, are usually limited to some fairly large number. During a subsequent pass, the set of virtual registers are assigned to a set of physical registers. For situations when the number of virtual registers is less than or equal to the number of physical registers, assigning the set of virtual registers to the set of physical registers is relatively simple. However, when the number of virtual registers exceeds the number of available physical registers, then the set of virtual registers must be mapped to the set of physical registers. In the context of compilers, mapping a set of virtual registers to a set of physical registers refers to determining an assignment of the set of virtual registers to the set of physical registers so that all computations specified by this code can be performed in the set of physical registers.
One approach for mapping a set of virtual registers to a set of physical registers is known as the graph coloring approach which is described in U.S. Pat. No. 4,571,678 issued to Chaitin on Feb. 18, 1986. Generally, the graph coloring approach involves constructing and analyzing a register interference graph for each portion of the code. The register interference graph includes a number of nodes which represent the virtual registers. Pairs of nodes in the graph are connected when two variables represented by the nodes cannot simultaneously share a physical register at some point in time during the execution of the code, effectively representing a conflict between the two nodes.
The register interference graph is then analyzed and nodes having fewer connections than the number of available physical registers are removed from the graph. If all of the nodes can be removed from the graph, then a coloring can be determined. That is, all of the virtual registers can be mapped to physical registers. However, sometimes the register interference graph contains one or more nodes having more connections than the number of available physical registers. This means that the number of available hardware registers is insufficient to store all of the intermediate values specified by the code. Thus, some intermediate values must be stored in another storage medium such as memory.
The process of temporarily storing data to another storage medium such as memory is referred to as "spilling." Generally, spilling involves performing a spill operation, followed by one or more reload operations. The spill operation causes some specified data to be stored from a physical register into another storage medium, such as a runtime stack in memory. Each reload operation causes the specified data to be loaded or copied from the other storage medium into a physical register. Reload operations are typically performed when the specified data is required for a calculation.
In terms of the register interference graph, a spill is reflected in the graph by disconnecting a node from all other nodes and removing that node from the graph. Then the graph is rebuilt and analyzed again. This process is repeated until a mapping of the set of virtual registers to the set of physical registers is determined.
The high level approach for mapping a set of virtual registers to a set of physical registers according to the graph coloring approach is illustrated by the flow chart of FIG. 1. After starting in step 100, a register interference graph is built in step 102. Then in step 104, the register interference graph is analyzed. As previously described, analyzing the register interference graph involves removing any nodes which have fewer connections to other nodes than the number of available physical registers.
In step 106, a determination is made as to whether the register interference graph can be colored. As previously discussed, if all of the nodes can be removed from the graph, indicating that there are no conflicts, then the graph can be colored. If so, then the process is complete in step 108. On the other hand, if in step 106 the graph cannot be colored, then in step 110, one of the virtual registers is spilled, which eliminates the spilled register as a conflicted node in the graph. In step 112 the register interference graph is rebuilt and then steps 104 through 112 are repeated until the register graph is colored.
The Problem
Although the spilling approach allows a set of virtual registers to be mapped to a set of physical registers, the approach does have some disadvantages. One disadvantage is that write and read operations to secondary storage mediums, such as runtime stacks, often take more time to execute than write and read operations to central processing unit (CPU) registers. Furthermore, additional instructions must be executed to perform the spill and reload operations. This increases the overall time required to process a sequence of instructions which provide for the spilling of data.
Consider the example illustrated by FIGS. 2A and 2B. A code block 200 includes code 202 which defines a variable X. Code block 200 also includes code 204, 206, 208 and 210, which use the variable X. Code block 200 may also include other code which is not illustrated.
FIG. 2B illustrates code block 200 which has been modified to reflect the spilling of variable X. Specifically, code 212 has been added immediately following code 202, to perform a spill operation on the variable X. As previously discussed, spilling a variable involves writing the variable from a physical register to another storage medium, such as a runtime stack in memory.
In addition, code 214 has been added immediately before code 204 to perform a reload operation on the variable X, which causes the variable X to be reloaded into a hardware register as X'. Code 204 then uses the reloaded variable X'. Similarly, code 216 has been added immediately before code 206 to reload the variable X as X", which is then used by code 206. Also, code 218 and 220 have also been added to reload the variable X as X'" and X"", respectively.
As is illustrated by code block 200 in FIG. 2B, the spilling of variable X involves both writing the variable X from a physical register to a memory location (a spill operation), but also reloading the variable X in each instance where the variable X is used in code block 200. This can adversely affect performance when a reload operation is added to a portion of code which is repeated many times, such as a loop.
In view of the need for spilling virtual registers to allow the mapping of a set of virtual registers to a set of physical registers, there is a need for an approach for allocating a set of virtual registers to a set of physical registers that reduces spilling.